/*
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#pragma once
#include "../Vector3i.h"
#include "../NTree.h"
#include "../Relations.h"
#include "BoxTests.h"

template<class VecType>
class Sphere
{
private:
	const typename VecType::scalarType rSquared;
	const VecType vPos;
	const Box<VecType> aabb;
	const Box<VecType> aabbSq;//AABB in squared coords
public:

	RangeRelation
	testBoxSquared(const Box<VecType>& squaredBox) const
	{
		//check bounds
		RangeRelation aabbRel=BoxTests<VecType>::boxRelation(squaredBox, aabbSq);
		switch(aabbRel)
		{
		case Surrounds:
			return Surrounds;
		case Outside:
			return Outside;
		default:
			break;
		}

		//for each face of the box
		int nInside=0;
		int nOutside=0;
		int nTested=0;
		Box<typename VecType::lowerDim> rectSq;
		typename VecType::scalarType distSq;

		for (unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
		{
			for (int iDir = 0; iDir < 2; iDir++)
			{
				if(iDir)
					distSq=squaredBox.max.getComponent(iDim);
				else
					distSq=squaredBox.min.getComponent(iDim);

				for (unsigned int i = 0, j=0; i < VecType::dimension; i++)
				{
					if(i==iDim)
						continue;
					rectSq.min[j]=squaredBox.min.getComponent(i);
					rectSq.max[j]=squaredBox.max.getComponent(i);
					j++;
				}
				//project radius
				const typename VecType::scalarType projectedRSquared=rSquared-abs(distSq);
				if(projectedRSquared<0)
					continue;//this geometry can not be intersected by the sphere/circle

				//test axis aligned rectangle
				RangeRelation rel;
				if(VecType::lowerDim::dimension==1)
					//the given rect is a line
					rel=checkRanges(rectSq.min.getComponent(0),
									rectSq.max.getComponent(0),
									-projectedRSquared, projectedRSquared);
				else
					rel=Sphere<typename VecType::lowerDim>(projectedRSquared).testBoxSquared(rectSq);


				switch(rel)
				{
				case Inside:
					nInside++;//should not occur
					break;
				case Outside:
					nOutside++;
					break;
				default:
					return Overlaps;
				}
				nTested++;
			}
		}
		if(nOutside==nTested)
			return Outside;
		//mixed, should not happen
		return Overlaps;
	}

	Sphere(const float radius, const VecType& vPos) : rSquared((typename VecType::scalarType)(radius*radius)),
							vPos(vPos), aabb(vPos-VecType((typename VecType::scalarType)radius), vPos+VecType((typename VecType::scalarType)radius)),
							aabbSq(Box<VecType>(VecType((typename VecType::scalarType)(-radius*radius)), VecType((typename VecType::scalarType)(radius*radius))))
	{}

	//aabb will be invalid
	Sphere(const typename VecType::scalarType rSquared) : rSquared(rSquared),
								vPos(VecType(0)), aabb(VecType(0), VecType(0)),
								aabbSq(Box<VecType>(VecType(-rSquared), VecType(rSquared)))
	{}

	RangeRelation
	testPoint(const VecType& v) const
	{
		if((v-vPos).squaredLength()>rSquared)
			return Outside;
		return Inside;
	}

	//box' relation to the sphere
	RangeRelation
	testBox(const Box<VecType>& testBox) const
	{
		//level 0 gate
		if(testBox.min==testBox.max)
			return testPoint(testBox.min);

		VecType vMin=testBox.min-vPos;
		VecType vMax=testBox.max-vPos;

		//normally, you would test each corner of the box
		//here, a little optimization is used.
		//since testing against the sphere means checking the squared
		//sum of the component, just get min and max here
		typename VecType::scalarType rSqMin=0;
		typename VecType::scalarType rSqMax=0;

		for(unsigned int iDim = 0; iDim < VecType::dimension; iDim++)
		{
			//square vector components
			typename VecType::scalarType& mi=vMin[iDim];
			typename VecType::scalarType& ma=vMax[iDim];
			mi*=abs(mi);
			ma*=abs(ma);

			const typename VecType::scalarType
				x1=abs(mi),
				x2=abs(ma);

			if(x1>x2)
			{
				rSqMax+=x1;
				rSqMin+=x2;
			}
			else
			{
				rSqMax+=x2;
				rSqMin+=x1;
			}
		}
		//now compare
		if(rSqMin<=rSquared)
		{
			if(rSqMax<=rSquared)
				return Inside;
			else
				return Overlaps;
		}
		//now all box vertices are outside
		//there can still be overlapping cases
		//due to the box faces intersecting with the sphere

		return testBoxSquared(Box<VecType>(vMin, vMax));
	}

	Box<VecType>
	getBounds() const
	{
		return aabb;
	}
};
